1. Field of the Invention
The invention relates to computer systems in general and, more particularly, to computer methods and systems for solving sets of equations that can be represented in matrix form.
2. Description of the Related Art
Solving sets of equations is useful in, inter alia, mechanics, economics, fluid dynamics and electric circuit simulation. Circuit simulation, for example, typically involves assembling a set of equations that model the behavior of an electric circuit and then solving such set of equations to learn the value of unknown voltages and currents in the circuit. The equations that describe the circuit being simulated are often nonlinear and, for this reason, an iterative technique, such as the Newton Raphson method has typically been used to solve such set of equations. Various iterative techniques, including the Newton Raphson method, are well known to persons having ordinary skill in the art.
One part of the Newton Raphson method involves solving a set of linear equations. Empirically, the time needed to solve the set of equations dominates the time needed to simulate a large circuit. Using conventional circuit simulation techniques, even the most powerful supercomputers take many hours to complete a simulation and therefore, the simulation of large integrated circuits is still impractical.
Although a number of methods can be used to solve a set of linear equations, Lower Upper Decomposition ("LUD"), a method well known to persons having ordinary skill in the art, is generally preferred because of its accuracy and stability. LUD, however, cannot be parallelized easily.
A number of efforts have been made to parallelize LUD. J. Huang and O. Wing, "Optimal Parallel Triangulation of a Sparse Matrix," I.E.E.E. Trans. on Circuits and Systems, Vol. CAS-26, pp. 726-732 (Sept. 1979); N. Karmarkar, "A New Parallel Computer for Sparse Matrix Computation," Siam Conference on Discrete Mathematics, Atlanta (June 1990); and O. Wing and J. Huang, "A Computation Model of Parallel Solution of Linear Equations," I.E.E.E. Trans. on Computers, Vol. C-29, pp. 632-638 (July 1980). These methods concentrate on precompiling each step required in LUD and constructing a task graph which is then scheduled to run on a multiprocessor. These procedures yield a large number of tasks that need to be scheduled and require too much computer memory for realistic circuits.
An alternative approach, proposed by P. Sadayappan and V. Visvanathan, "Circuit Simulation on Shared Memory Multiprocessors," I.E.E.E. Transactions on Computers, Vol. C-37, pp. 1634-1642 (Dec. 1988), uses a partially compiled approach which has been shown to be very effective in extracting a high degree of parallelism from LUD of sparse matrices while minimizing the complexity of the task graph that has to be scheduled. This approach is a good compromise between the generic LUD approach and the compiled approach.
The Sadayappan-Visvanathan approach was originally developed for a shared memory multiprocessor and extended for use on a distributed memory multiprocessor in J. Trotter and P. Agrawal, "Circuit Simulation Methods on a Distributed Memory Multiprocessor System," I.E.E.E. Proceedings ICCAD, Santa Clara, pp. 438-441 (Nov. 1990). This reference is hereby incorporated by paper into this specification.
Another approach proposed by T. Nakata, N. Tanabe, H. Onozuka, T. Kurobe and N. Koike in "A Multiprocessor System for Modular Circuit Simulation," I.E.E.E. ICCAD, pp. 364-367 (1987), used LUD without compilation on a distributed memory multiprocessor. In the Nakata et. al. system each processor can access the memory of other processors using a shared bus.